The term “Turing machine” refers to a theoretical computing device that performs computations in a manner first postulated by Alan Turing. Most modern electrical computers are instantiations of Turing machines. In general, a Turing machine may be understood as a device that has the ability to read symbols stored on, and to write symbols onto, an endless tape. The tape may be initialized to contain one or more symbols. Furthermore, the Turing machine has a “state” which may change over time. Often such states are described using simple labels, such as numbers (e.g., states 1, 2, and 3) or letters (e.g., states A, B, and C), but the particular labels that are used to identify states is not important.
As described in more detail in U.S. Pat. No. 9,342,788, which is hereby incorporated by reference herein, a Turing machine may be deterministic or nondeterministic. In a deterministic Turing machine, the set of rules that is associated with the Turing machine unambiguously specify the action(s) to be performed for each state-input combination. In contrast, the rules associated with a non-deterministic Turing machine (NTM) may specify two or more alternate actions to be performed for a state-input combination.
As the description above implies, in a deterministic Turing machine, the combination of the current state and current input uniquely (i.e., unambiguously) specify the symbol (if any) to be written at the current position, the direction (if any) to move the head, and the new state of the Turing machine (which may be the same as the current state). As the description above further implies, in a nondeterministic Turing machine, the combination of the current state and current input do not necessarily uniquely specify the symbol (if any) to be written at the current position, the direction (if any) to move the head, and the new state of the Turing machine (which may be the same as the current state). A nondeterministic Turing machine is nondeterministic, therefore, because the combination of the current state and the current input do not necessarily determine the symbol to be written by the Turing machine at the current position, the Turing machine's next state, and the Turing machine's next position.
U.S. Pat. No. 9,342,788 discloses a nondeterministic Turing machine. In particular, U.S. Pat. No. 9,342,788 discloses techniques for constructing a nondeterministic Turing machine from a deterministic Turing machine. Such a nondeterministic Turing machine presents opportunities for solving a variety of problems.